//给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。 
//
// 两个相邻元素间的距离为 1 。 
//
// 
//
// 示例 1： 
//
// 
//
// 
//输入：mat = [[0,0,0],[0,1,0],[0,0,0]]
//输出：[[0,0,0],[0,1,0],[0,0,0]]
// 
//
// 示例 2： 
//
// 
//
// 
//输入：mat = [[0,0,0],[0,1,0],[1,1,1]]
//输出：[[0,0,0],[0,1,0],[1,2,1]]
// 
//
// 
//
// 提示： 
//
// 
// m == mat.length 
// n == mat[i].length 
// 1 <= m, n <= 10⁴ 
// 1 <= m * n <= 10⁴ 
// mat[i][j] is either 0 or 1. 
// mat 中至少有一个 0 
// 
//
// 
//
// 
// 注意：本题与主站 542 题相同：https://leetcode-cn.com/problems/01-matrix/ 
//
// Related Topics 广度优先搜索 数组 动态规划 矩阵 👍 66 👎 0


package LeetCode.editor.cn;


import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

/**
 * @author ldltd
 * @date 2025-04-03 15:50:28
 * @description LCR 107.01 矩阵
 
 */
 
public class TwoBCMpM {
    public static void main(String[] args) {
    //测试代码
    TwoBCMpM fun = new TwoBCMpM();
    Solution solution= fun.new Solution();
    solution.updateMatrix(new int[][]{{0},{1}});
    }

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
        //从每一个1开始bfs，但是可能会有重复计算
    public int[][] updateMatrix2(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        int [] dx=new int[]{-1,0,1,0};
        int [] dy=new int[]{0,1,0,-1};
        int [][] res=new int[m][n];
        ArrayDeque<int []> q=new ArrayDeque<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(mat[i][j]==0) {
                    res[i][j]=0;
                    continue;
                }
                boolean flag=false;
                q.offer(new int[]{i,j,1});
                // 每次 BFS 前初始化 visited 数组
                boolean[][] visited = new boolean[m][n];
                while (!q.isEmpty()&&!flag){
                    int[] poll = q.poll();
                    for (int k = 0; k < 4; k++) {
                        int x=poll[0]+dx[k];
                        int y=poll[1]+dy[k];
                        if(x>=0&x<m&&y>=0&&y<n&& !visited[x][y]){
                            if(mat[x][y]==0){
                                flag=true;
                                res[i][j]=poll[2];
                                break;
                            }
                            visited[x][y] = true;
                            q.offer(new int[]{x,y,poll[2]+1});
                        }
                    }
                }
                q.clear();
            }
        }
        return res;
    }
    //多源BFS，从所有0出发，计算所有1的最短距离
    public int[][] updateMatrix1(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        int [][]res=new int[m][n];
        ArrayDeque<int []> q=new ArrayDeque<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(mat[i][j]==0){
                    q.offer(new int[]{i,j});
                    res[i][j]=0;
                }else {
                    res[i][j]=-1;
                }

            }
        }
        int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
        while (!q.isEmpty()){
            int [] cur=q.poll();
            int x=cur[0],y=cur[1];
            for (int i = 0; i < 4; i++) {
                int nx=x+dx[i],ny=y+dy[i];
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && res[nx][ny] == -1) {
                    res[nx][ny] = res[x][y] + 1;
                    q.offer(new int[]{nx, ny});
                }
            }
        }
        return res;
    }
    /*
    * 动态规划
    * dp[i][j]表示到0的最短距离
    * 然后两阶段dp
    * 单方向dp可能路径遗漏
    * 第一阶段左上到右下，
    * 第二阶段右下到坐上
    * 两次遍历保证了一定来自四周最近的一个
    * */
    public int[][] updateMatrix(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        int[][] res = new int[m][n];
        ArrayDeque<int[]> q = new ArrayDeque<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 0) {
                    q.offer(new int[]{i, j});
                    res[i][j] = 0;
                } else {
                    res[i][j] = m*n+1;
                }

            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(mat[i][j]==1){
                    if(i>0){
                        res[i][j]=Math.min(res[i][j],res[i-1][j])+1;
                    }
                    if(j>0){
                        res[i][j]=Math.min(res[i][j],res[i][j-1])+1;
                    }
                }
            }
        }

        for (int i = m-1; i>=0; i--) {
            for (int j = n-1; j >=0; j--) {
                if(mat[i][j]==1){
                    res[i][j]=Math.min(Math.min(res[i][j],res[i+1][j]),res[i][j+1])+1;
                }
            }
        }
        return res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
